package leetcode.editor.cn;

//给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。 
//
// 
//
// 注意： 
//
// 
// 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2 
// 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2³¹, 2³¹−1]。本题中，如果除法结果溢出，则返回 231 − 1 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：a = 15, b = 2
//输出：7
//解释：15/2 = truncate(7.5) = 7
// 
//
// 示例 2： 
//
// 
//输入：a = 7, b = -3
//输出：-2
//解释：7/-3 = truncate(-2.33333..) = -2 
//
// 示例 3： 
//
// 
//输入：a = 0, b = 1
//输出：0 
//
// 示例 4： 
//
// 
//输入：a = 1, b = 1
//输出：1 
//
// 
//
// 提示: 
//
// 
// -2³¹ <= a, b <= 2³¹ - 1 
// b != 0 
// 
//
// 
//
// 注意：本题与主站 29 题相同：https://leetcode-cn.com/problems/divide-two-integers/ 
//
// 
// 👍 52 👎 0


public class POffer001Xoh6Oh{
	public static void main(String[] args) {
		Solution solution = new POffer001Xoh6Oh().new Solution();
		int divide = solution.divide_bats(
				-15, 2);
		System.out.println(divide);
	}
	
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	/**
	 * O(n)
	 * @param a
	 * @param b
	 * @return
	 */
	public int divide_bats(int a, int b) {
		boolean sign = (a > 0) ^ (b > 0);
		// 防止越界
		if (a == Integer.MIN_VALUE && b == -1) {
			return Integer.MAX_VALUE;
		}
		// 负数最小值 绝对值还是负数，所以要用无符号右移做除法
		a = Math.abs(a);
		b = Math.abs(b);
		int q = 0;
		int n = 31;
		while (n >= 0) {
			// >>> 无符号右移，保证a最小值和b最小值时能保证数据正确
			if ((a >>> n) - b >= 0) { // 2<<31会越界，a >= (b << n) 改写成a右移，保证不越界
				a = a - (b << n);
				q += 1 << n;
			}
			n--;
		}
		return sign ? -q : q;
	}

	/**
	 * O(logn)
	 * @param a
	 * @param b
	 * @return
	 */
    public int divide(int a, int b) {
		boolean sign = (a > 0) ^ (b > 0);
		// 防止越界
		if (a == Integer.MIN_VALUE && b == -1) {
			return Integer.MAX_VALUE;
		}
		// 因为abs(−2^31) > 231−1，所以最小数转正数会越界
		if (a > 0)
			a = -a;
		if (b > 0)
			b = -b;
		int q = 0;
		while (a <= b) {
			int value = b;
			int n = 1;
			while (value >= -1073741824 && a <= (value + value)) {
				value += value;
				n += n;
			}
			a = a - value;
			q += n;
		}
		return sign ? -q : q;
    }

	/**
	 * O(n)
	 * @param a
	 * @param b
	 * @return
	 */
	public int divide_overtime(int a, int b) {
		boolean sign = (a > 0) ^ (b > 0);
		// 防止越界
		if (a == Integer.MIN_VALUE && b == -1) {
			return Integer.MAX_VALUE;
		}
		// 因为abs(−2^31) > 231−1，所以最小数转正数会越界
		if (a > 0)
			a = -a;
		if (b > 0)
			b = -b;
		int q = 0;
		while (a <= b) {
			a = a - b;
			q += 1;
		}
		return sign ? -q : q;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}